4.9 Negation in Prolog

Prolog implements “negation as failure.” That is, to check that a formula is false, we simply pretend to execute it (succeeding or failing), and then do the opposite (failing or succeeding).

This sounds simple, but it has some surprising consequences that mean we must be very careful in how we write Prolog code involving negations.

Definition

If Q is an arbitrary query, then \+ Q is its negation and does the opposite.

\+ Q never defines any variables; if Q succeeds, we backtrack, and if Q fails (and hence sets no variables) we continue.

Example

Suppose we load the family tree database that includes Simpsons characters (where bart has siblings lisa and maggie, but ug has no siblings). Then:

\+ sib(bart, lisa).

Fails, because sib(bart, lisa) would succeed.

\+ sib(bart, homer).

Succeeds, because sib(bart, homer) fails.

\+ sib(bart, X).

Fails (without defining X ), because the query sib(bart, X) can succeed in multiple ways.

X=homer, \+ sib(bart, X).

Succeeds (and sets X = homer), because by the query sib(bart, X) fails when X has already been defined to be the non-sibling homer.

\+ sib(ug, X).

Succeeds (without defining X) because sib(ug, X) fails.

Sometimes it’s easier to define not the property we want, but its negation. In that case, we can define a the negated property as a helper predicate, and then use the \+ operator.

Example

Our family-tree database contains one fact age(Person,Age). for each person in the genealogy. How could we find the oldest person in our database (i.e., skugerina, aged 101)?

First try:
```
oldest(X) :- AgeX > AgeY, age(X,AgeX), age(Y,AgeY).
```
If we run the query oldest(P), the code will immediately crash because the first thing this predicate does is compare the values of two uninitialized variables AX and AY.
Second try:
```
oldest(X) :- age(X,AgeX), age(Y,AgeY), AgeX > AgeY.
```
By moving the comparison to the end (after AgeX and AgeY have values determined by the age predicates), the code will no longer crash.

However, since the variable Y appears only in the premise of this rule (the right-hand side), we definition as follows: X is oldest if there exists some Y whose age is greater than X’s age.

So this is not a definition of the oldest predicate, but rather a definition of notYoungest!
Third try:
```
notOldest(X) :- age(X,AgeX), age(Y,AgeY), AgeX < AgeY.
oldest(X) :- \+ notOldest(X).
```
Using the idea of the previous attempt and flipping the comparison lets us define a notOldest predicate (i.e., X is not oldest if there exists a strictly older Y).

Then we just say that X is oldest if X is not notOldest.

This works somewhat. Certainly oldest(skugerina) succeeds (because notOldest(skugerina) fails as there is no valid choice of Y, and oldest(bart) or any other person correctly fails.

The only problem is that if we try to discover the oldest person in the database with the query oldest(P), the query fails. The problem is that the query notOldest(P) succeeds in multiple ways (there are lots of people who are not oldest!), so its negation fails.
Final try:
```
notOldest(X) :- age(X,AgeX), age(Y,AgeY), AgeX < AgeY.
person(X) :- age(X, _).
oldest(X) :- person(X), \+ notOldest(X).
```
Here we have defined a second helper predicate for detecting whether the input is a person in the database (since every person has an age).

If we ask about a specific person (e.g., oldest(skugerina) or oldest(bart)) then the code will correctly succeed or fail as above, with just an extra double-check that the person is in the database.

But now if we run the query oldest(P), the code has a generate and test format. The first part will set P to a specific person in the database, which means the second part can correctly determine if they are oldest. If not, we backtrack and try a different specific person P, until we find one who is oldest.

The moral of this story is that we should make sure that variables involved are given values before we attempt to use them in a negation or inequality. This means negations (and inequalities!) should be placed toward the end of our rules, e.g.,